{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14-1 Point of maximum overlap\n",
    "\n",
    "> Suppose that we wish to  keep track of a point of maximum overlap in a set of intervals - a point with the largest number of intervals in the set that overlap it.\n",
    "\n",
    "> __*a*__. Show that there will always be a point of maximum overlap that is an endpoint of one of the segments.\n",
    "\n",
    "> __*b*__. Design a data structure that efficiently supports the operations INTERVAL-INSERT, INTERVAL-DELETE, and FIND-POM, which returns a point of maximum overlap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 14-2 Josephus permutation\n",
    "\n",
    "> We define the __*Josephus problem*__ as follows. Suppose that $n$ people form a circle and that we are given a positive integer $m \\ge n$. Beginning with a designated first person, we proceed around the circle, removing every $m$th person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all $n$ people. The order in which the people are removed from the circle defines the __*$(n,m)$-Josephus permutation*__ of the integers $1,2, \\dots ,n$. For example, the $(7, 3)$-Josephus permutation is $\\langle 3, 6, 2, 7, 5, 1, 4 \\rangle$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*a*__. Suppose that $m$ is a constant. Describe an $O(n)$-time algorithm that, given an integer $n$, outputs the $(n,m)$-Josephus permutation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use doubly linked list, the time is $O(nm)$, since $m$ is a constant, $O(nm)$ = $O(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class LinkedListNode:\n",
    "    def __init__(self, key):\n",
    "        self.key = key\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def insert(self, key):\n",
    "        x = LinkedListNode(key)\n",
    "        if self.head is None:\n",
    "            self.head = x\n",
    "            x.next = x\n",
    "            x.prev = x\n",
    "        else:\n",
    "            x.prev = self.head.prev\n",
    "            x.next = self.head\n",
    "            x.prev.next = x\n",
    "            x.next.prev = x\n",
    "\n",
    "    def remove(self):\n",
    "        if self.head.next == self.head:\n",
    "            self.head = None\n",
    "        else:\n",
    "            self.head.next.prev = self.head.prev\n",
    "            self.head.prev.next = self.head.next\n",
    "            self.head = self.head.next\n",
    "\n",
    "    def forward(self, step):\n",
    "        while step > 0:\n",
    "            step -= 1\n",
    "            self.head = self.head.next\n",
    "\n",
    "\n",
    "def josephus_permutation(n, m):\n",
    "    lst = LinkedList()\n",
    "    for i in xrange(1, n + 1):\n",
    "        lst.insert(i)\n",
    "    perm = []\n",
    "    while lst.head is not None:\n",
    "        lst.forward(m - 1)\n",
    "        perm.append(lst.head.key)\n",
    "        lst.remove()\n",
    "    return perm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __*b*__. Suppose that $m$ is not a constant. Describe an $O(n \\lg n)$-time algorithm that, given integers $n$ and $m$, outputs the $(n,m)$-Josephus permutation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Build a balanced binary search tree in $O(n \\lg n)$, maintain $size$ to support order-statistics. In each iteration, we select and delete the $(r + m - 1) ~\\text{mod}~ T.root.size + 1$th element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, key, left=None, right=None):\n",
    "        self.key = key\n",
    "        self.color = BLACK\n",
    "        self.size = 1\n",
    "        self.p = None\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        if left is not None:\n",
    "            left.p = self\n",
    "            self.size += left.size\n",
    "        if right is not None:\n",
    "            right.p = self\n",
    "            self.size += right.size\n",
    "\n",
    "\n",
    "class BinarySearchTree:\n",
    "    def __init__(self, a):\n",
    "        self.root = self.build(a, 0, len(a))\n",
    "\n",
    "    def build(self, a, l, r):\n",
    "        if l >= r:\n",
    "            return None\n",
    "        mid = (l + r) // 2\n",
    "        return TreeNode(a[mid], self.build(a, l, mid), self.build(a, mid+1, r))\n",
    "\n",
    "    def get_size(self, x):\n",
    "        if x is None:\n",
    "            return 0\n",
    "        return x.size\n",
    "\n",
    "    def update_size(self, x):\n",
    "        if x is not None:\n",
    "            x.size = 1 + self.get_size(x.left) + self.get_size(x.right)\n",
    "\n",
    "    def select(self, x, i):\n",
    "        r = self.get_size(x.left) + 1\n",
    "        if i == r:\n",
    "            return x\n",
    "        elif i < r:\n",
    "            return self.select(x.left, i)\n",
    "        else:\n",
    "            return self.select(x.right, i - r)\n",
    "\n",
    "    def minimum(self, x):\n",
    "        while x.left is not None:\n",
    "            x = x.left\n",
    "        return x\n",
    "\n",
    "    def transplant(self, u, v):\n",
    "        if u.p is None:\n",
    "            self.root = v\n",
    "        elif u == u.p.left:\n",
    "            u.p.left = v\n",
    "        else:\n",
    "            u.p.right = v\n",
    "        if v is not None:\n",
    "            v.p = u.p\n",
    "\n",
    "    def delete(self, z):\n",
    "        if z.left is None:\n",
    "            self.transplant(z, z.right)\n",
    "        elif z.right is None:\n",
    "            self.transplant(z, z.left)\n",
    "        else:\n",
    "            y = self.minimum(z.right)\n",
    "            p = y.p\n",
    "            if y.p != z:\n",
    "                self.transplant(y, y.right)\n",
    "                y.right = z.right\n",
    "                y.right.p = y\n",
    "            self.transplant(z, y)\n",
    "            y.left = z.left\n",
    "            y.left.p = y\n",
    "            while p != z and p != y:\n",
    "                self.update_size(p)\n",
    "                p = p.p\n",
    "            self.update_size(y)\n",
    "        while z.p is not None:\n",
    "            z = z.p\n",
    "            self.update_size(z)\n",
    "\n",
    "\n",
    "def josephus_permutation(n, m):\n",
    "    tree = BinarySearchTree(range(1, n + 1))\n",
    "    perm = []\n",
    "    rank = 0\n",
    "    while n > 0:\n",
    "        rank = (rank + m - 1) % n\n",
    "        x = tree.select(tree.root, rank + 1)\n",
    "        perm.append(x.key)\n",
    "        tree.delete(x)\n",
    "        n -= 1\n",
    "    return perm"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
